#include <iostream>
#include <vector>
#include <list>
#include <utility>

template<typename Key, typename Value>
class MyUnorderedMap {
private:
    using KeyValuePair = std::pair<Key, Value>;
    using Bucket = std::list<KeyValuePair>;
    using BucketIterator = typename Bucket::iterator;

    std::vector<Bucket> buckets;
    size_t size;

    size_t hash(const Key& key) const {
        // TODO: Implement your own hash function
        // Return the hash value for the given key
    }

    BucketIterator findBucket(const Key& key) {
        size_t index = hash(key) % buckets.size();
        Bucket& bucket = buckets[index];
        for (auto it = bucket.begin(); it != bucket.end(); ++it) {
            if (it->first == key) {
                return it;
            }
        }
        return bucket.end();
    }

public:
    MyUnorderedMap(size_t capacity = 10) : buckets(capacity), size(0) {}

    void insert(const Key& key, const Value& value) {
        BucketIterator it = findBucket(key);
        if (it != buckets[hash(key) % buckets.size()].end()) {
            it->second = value; // Key already exists, update the value
        } else {
            buckets[hash(key) % buckets.size()].emplace_back(key, value);
            ++size;
        }
    }

    bool erase(const Key& key) {
        BucketIterator it = findBucket(key);
        if (it != buckets[hash(key) % buckets.size()].end()) {
            buckets[hash(key) % buckets.size()].erase(it);
            --size;
            return true;
        }
        return false;
    }

    Value& operator[](const Key& key) {
        BucketIterator it = findBucket(key);
        if (it != buckets[hash(key) % buckets.size()].end()) {
            return it->second;
        } else {
            buckets[hash(key) % buckets.size()].emplace_back(key, Value());
            ++size;
            return buckets[hash(key) % buckets.size()].back().second;
        }
    }

    size_t getSize() const {
        return size;
    }
};

int main() {
    MyUnorderedMap<int, std::string> myMap;

    myMap.insert(1, "apple");
    myMap.insert(2, "banana");
    myMap.insert(3, "cherry");

    std::cout << "Value at key 2: " << myMap[2] << std::endl;

    myMap[2] = "grape";

    myMap.erase(3);

    for (const auto& pair : myMap) {
        std::cout << "Key: " << pair.first << ", Value: " << pair.second << std::endl;
    }

    return 0;
}
